import java.io.IOException;
import java.util.ArrayList;

public class 附加题 {
    public static ArrayList<String> list = new ArrayList<>();

    public static void dfs(int sum, String str, int idx, int[] arr, int target) {
        if (idx >= arr.length) {
            if (sum == target) {
                list.add(str + "=100");
            }
            return;
        }

        sum += arr[idx];
        String res = "+" + arr[idx];
        str += res;
        dfs(sum, str, idx + 1, arr, target);

        sum -= arr[idx] * 2;
        str = str.substring(0, str.length() - res.length());
        res = "-" + arr[idx];
        str += res;
        dfs(sum, str, idx + 1, arr, target);

        if(idx <= arr.length - 2){
            sum += arr[idx];
            str = str.substring(0,str.length() - res.length());
            sum += (arr[idx] * 10 + arr[idx + 1]);
            str += ("+" + arr[idx] + arr[idx + 1] );
            dfs(sum, str, idx + 2, arr, target);
        }

        if(idx <= arr.length - 3){
            sum += arr[idx];
            str = str.substring(0,str.length() - res.length());
            sum += (arr[idx] * 100 + arr[idx + 1] * 10 + arr[idx + 2]);
            str += ("+" + arr[idx] + arr[idx + 1] + arr[idx + 2] );
            dfs(sum, str, idx + 3, arr, target);
        }

    }

    public static void main(String[] args) throws IOException {

        long start = System.currentTimeMillis();

        int[] arr = {9, 8, 7, 6, 5, 4, 3, 2, 1};
        int sum = 100;

        dfs(0, "", 0, arr, sum);

        long end = System.currentTimeMillis();

        System.out.println("耗时: " + ((end - start) * 1.0 / 1000) +"秒" );
        System.out.println("有"+ list.size() + "情况");

        for (String str : list) {
            System.out.println(str);
        }
    }
}

